class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = [i for i in nums if i != 0]
        length = len(nums)
        if length == 0:
            return 0
        nums.append(1)
        dp = [[0] * length for _ in range(length)]
        for i in range(length):
            dp[i][i] = nums[i-1] * nums[i] * nums[i+1]
        for stride in range(1, length):
            for begin in range(length - stride):
                end = begin + stride
                maxResult = 0
                for i in range(begin, end + 1):
                    result = nums[begin-1] * nums[i] * nums[end+1]
                    if begin <= i-1:
                        result += dp[begin][i-1]
                    if end >= i+1:
                        result += dp[i+1][end]
                    maxResult = max(maxResult, result)
                dp[begin][end] = maxResult
        return dp[0][length-1]

s = Solution()
print(s.maxCoins([3, 1, 5, 8]))
